import java.util.List;

// 测试类，用于验证 BinaryTree 的功能
public class BinaryTreeTest {

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        BinaryTree.TreeNode root = tree.createTree(); // 创建测试树

        System.out.println("========== 遍历测试 ==========");
        System.out.print("前序遍历预期[A B D E H C F G ]: ");
        tree.preOrder(root); // 预期输出：A B D E H C F G
        System.out.println();

        System.out.print("中序遍历预期[D B H E A F C G ]: ");
        tree.inOrder(root); // 预期输出：D B H E A F C G
        System.out.println();

        System.out.print("后序遍历预期[D H E B F G C A ]: ");
        tree.postOrder(root); // 预期输出：D H E B F G C A
        System.out.println("\n");

        System.out.println("========== 节点统计测试 ==========");
        tree.getNodeSize1(root);
        System.out.println("遍历法节点数(预期8): " + tree.nodeSize);
        System.out.println("子问题法节点数(预期8): " + tree.getNodeSize2(root));

        tree.getLeafNodeCount1(root);
        System.out.println("遍历法叶子数(预期4): " + tree.leafCount);
        System.out.println("子问题法叶子数(预期4): " + tree.getLeafNodeCount2(root));

        System.out.println("第3层节点数(预期4): " + tree.getKLevelNodeCount(root, 3));
        System.out.println("树高度(预期4): " + tree.getHeight1(root) + "\n");

        System.out.println("========== 节点查找测试 ==========");
        System.out.println("查找存在的节点'H'(预期H): " + tree.find(root, 'H').val);
        System.out.println("查找不存在的节点'I'(预期null): " + tree.find(root, 'I') + "\n");

        System.out.println("========== 结构判断测试 ==========");
        System.out.println("相同树判断(预期true): " + tree.isSameTree(root, tree.createTree()));

        // 直接使用 new BinaryTree.TreeNode(...) 实例化静态内部类
        BinaryTree.TreeNode subRoot = new BinaryTree.TreeNode('B');
        subRoot.left = new BinaryTree.TreeNode('D');
        subRoot.right = new BinaryTree.TreeNode('E');
        subRoot.right.right = new BinaryTree.TreeNode('H');
        System.out.println("子树判断(预期true): " + tree.isSubtree(root, subRoot));

        System.out.println("平衡树判断(预期true): " + tree.isBalanced2(root));
        System.out.println("对称树判断(预期false): " + tree.isSymmetric(root) + "\n");

        System.out.println("========== 层序遍历测试 ==========");
        System.out.print("层序遍历预期[A B C D E F G H ]: ");
        tree.levelOrder(root); // 预期顺序：A B C D E F G H

        System.out.println("\n分层遍历结果:");
        List<List<Character>> levelList = tree.levelOrder2(root);
        for (List<Character> level : levelList) {
            System.out.println(level); // 预期分层: [A], [B,C], [D,E,F,G], [H]
        }
        System.out.println();

        System.out.println("========== 翻转二叉树测试 ==========");
        BinaryTree.TreeNode invertedRoot = tree.invertTree(root);
        System.out.print("翻转后的前序遍历预期[A C G F B E H D ]: ");
        tree.preOrder(invertedRoot); // 预期输出：A C G F B E H D
    }
}
